{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "p98LsLM6WO0h"
   },
   "source": [
    "## Search Exercise 6\n",
    "\n",
    "# The 8-Puzzle\n",
    "\n",
    "The 8-Puzzle is a simplified version of the better known\n",
    "[15-Puzzle](https://en.wikipedia.org/wiki/15_puzzle)\n",
    "invented by Noyes Palmer Chapman around 1874.\n",
    "Please refer to the Wikipedia page or other publically available \n",
    "sources for general information about the puzzle.\n",
    "\n",
    "In the 8-Puzzle we have 8 sliding tiles that can slide within in a 3x3\n",
    "grid, such that there is always one empty grid position, into which any\n",
    "of the neighbouring tiles can slide. The aim of the puzzle is to go from \n",
    "an intial randomised configuration of tiles to a specified end configuration,\n",
    "which typically has the tiles ordered in increasing order left to right and\n",
    "top to bottom, with the space being in at the bottom right.\n",
    "\n",
    "There is an interactive version with cheezy pictures that you can try \n",
    "[here](https://murhafsousli.github.io/8puzzle/#/) and an interactive \n",
    "8-Puzzle search algorithm demo can be found [here](https://deniz.co/8-puzzle-solver/).\n",
    "(This has a nice visualisation of the tree structure of the search spaces for several different algorithms.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EN9AS5C0WO0m"
   },
   "source": [
    "## Investigating search algorithm performance on the 8-Puzzle\n",
    "\n",
    "As with the other exercises, we start by installing `bbSearch` and importing the `SearchProblem` class and the `search` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "hRKYLHGtWO0n",
    "outputId": "6f5c09a5-a4a5-4cff-acc0-60c53aa7fc60"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100 18767  100 18767    0     0  11039      0  0:00:01  0:00:01 --:--:-- 11032\n",
      "Loading bbSearch Version 2.1 (at 21:46, Mon 07 Mar)\n",
      "Last module source code edit 9am Thursday 24th Feb 2022\n"
     ]
    }
   ],
   "source": [
    "!mkdir -p bbmodcache\n",
    "!curl http://bb-ai.net.s3.amazonaws.com/bb-python-modules/bbSearch.py > bbmodcache/bbSearch.py\n",
    "from bbmodcache.bbSearch import SearchProblem, search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-egmwdiUWO0o"
   },
   "source": [
    "### Representing a tile layout\n",
    "It is easy to represent the layout of tiles in a state by a list of lists structure. More precisely, we have a list of three lists representing each row; and each row list contains three numbers. We will use 0 to represent the empty space (into which neighbouring tiles may slide). Hence, we can define some layouts as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "1E5lbhDaWO0o"
   },
   "outputs": [],
   "source": [
    "## A couple of possible goal states:\n",
    "NORMAL_GOAL = [ [1,2,3],\n",
    "                [4,5,6],\n",
    "                [7,8,0] ]\n",
    "\n",
    "SPIRAL_GOAL = [ [1,2,3],\n",
    "                [8,0,4],\n",
    "                [7,6,5] ]\n",
    "\n",
    "### Declarations of some example states\n",
    "LAYOUT_0 = [ [1,5,2],\n",
    "             [0,4,3],\n",
    "             [7,8,6] ]\n",
    "\n",
    "LAYOUT_1 = [ [5,1,7],\n",
    "             [2,4,8],\n",
    "             [6,3,0] ] \n",
    "\n",
    "LAYOUT_2 = [ [2,6,3],\n",
    "             [4,0,5],\n",
    "             [1,8,7] ] \n",
    "\n",
    "LAYOUT_3 = [ [7,2,5],\n",
    "             [4,8,1],\n",
    "             [3,0,6] ] \n",
    "\n",
    "LAYOUT_4 = [ [8,6,7],  \n",
    "             [2,5,4],\n",
    "             [3,0,1] ] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zIn6qCEmWO0p"
   },
   "source": [
    "### A function for finding the position of a given number in a layout\n",
    "The following simple function will be useful. I will use it to find the position of the space (0), and **it will also be useful in defining heuristics**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "AlFlkB3PWO0q"
   },
   "outputs": [],
   "source": [
    "def number_position_in_layout( n, layout):\n",
    "    for i, row in enumerate(layout):\n",
    "        for j, val in enumerate(row):\n",
    "            if val==n:\n",
    "                return (i,j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ObOUWUPPWO0r"
   },
   "source": [
    "### Representing a state of the 8-Puzzle problem\n",
    "\n",
    "One could represent any state of the 8-puzzle simply by its tile layout. This contains all the information one may need to determine possible moves and to test whether it is a goal state.\n",
    "\n",
    "However, there is a drawback with using that representation. To calculate possible moves we need to know the position of the space, and although this is not difficult, it will take some computational effort to loop through the rows and columns of the layout representation to find the space. And if we do that thousands or even millions of times (as we might while searching a big search space), it could be computationally expensive. Hence, I represent an eight puzzle staid by a tuple of the form, \n",
    "`((row,col), layout)` where `(row,col)` gives the position of the space and `layout` is a list of lists representing the full layout, as specified above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "H2bzd_sUWO0r"
   },
   "source": [
    "## Define the `EightPuzzle` class\n",
    "\n",
    "As in previous examples we can define (by extending Brandon's `SearchProblem` class template) a class that specifies the structure of the 8-Puzzle in a way that can be handled by a variety of different search algorithms. \n",
    "\n",
    "The following brief notes will help you to understand the class definition in the next code cell:\n",
    "\n",
    "* Coordinates on the tile grid are given in the form `(row,column)`\n",
    "* The `action_dict` lists all possibles moves for each possible coordinate position\n",
    "  of where the space occurs in the grid. So, for example, if the space is at `(0,0)` we can either move the tile from `(1,0)` up, or move the tile from `(1,0)` left.\n",
    "  Specifying it like this should (I expect) be faster than \n",
    "  computing possible moves using a function (which might be used many many times during a big search).<br>\n",
    "* In `action_dict`, actions are specified by a tuple of the form `(row, col, d)`\n",
    "  giving the row and column of the moving piece and the\n",
    "  direction in which it moves. (The direction `d` could be calculated from `(row,col)` for any given board state, since we would know the possition of the space into which the moving tile moves, but it will make actions and movement paths easier to interpret if we add the direction to the action representation).\n",
    "  \n",
    "* The full representation for an action, used by the algorithm takes the form\n",
    "  `(row, col, (n, d))`. Here `n` is the number of the tile being moved and gets added to the action representation by the `possible_actions` function when it generates the possible actions from a given state. (Again this is not strictly necessary for the algorithm to work but make it much easier to interpret the sequences of moves it generates.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "H4y5H4brWO0t"
   },
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "class EightPuzzle( SearchProblem ):\n",
    "\n",
    "    # 左边是目标，右边是到左边的坐标的步骤\n",
    "    action_dict = {\n",
    "        (0,0) : [(1, 0, 'up'),    (0, 1, 'left')],\n",
    "        (0,1) : [(0, 0, 'right'), (1, 1, 'up'),    (0, 2, 'left')],\n",
    "        (0,2) : [(0, 1, 'right'), (1, 2, 'up')],\n",
    "        (1,0) : [(0, 0, 'down'),  (1, 1, 'left'),  (2, 0, 'up')],\n",
    "        (1,1) : [(1, 0, 'right'), (0, 1, 'down'),  (1, 2, 'left'), (2, 1, 'up')],\n",
    "        (1,2) : [(0, 2, 'down'),  (1, 1, 'right'), (2, 2, 'up')],\n",
    "        (2,0) : [(1, 0, 'down'),  (2, 1, 'left')],\n",
    "        (2,1) : [(2, 0, 'right'), (1, 1, 'down'),  (2, 2, 'left')],\n",
    "        (2,2) : [(2, 1, 'right'), (1, 2, 'down')]\n",
    "    }\n",
    "    \n",
    "    \n",
    "    def __init__(self, initial_layout, goal_layout ):\n",
    "        pos0 = number_position_in_layout( 0, initial_layout )\n",
    "        # Initial state is pair giving initial position of space\n",
    "        # and the initial tile layout.\n",
    "        self.initial_state = ( pos0, initial_layout)\n",
    "        self.goal_layout   = goal_layout\n",
    "        \n",
    "\n",
    "    ### I just use the position on the board (state[0]) to look up the \n",
    "    ### appropriate sequence of possible actions.\n",
    "    def possible_actions(self, state ):\n",
    "        actions =  EightPuzzle.action_dict[state[0]]\n",
    "        actions_with_tile_num = []\n",
    "        for r, c, d in actions:\n",
    "            tile_num = state[1][r][c] ## find number of moving tile\n",
    "            # construct the action representation including the tile number\n",
    "            actions_with_tile_num.append( (r, c, (tile_num,d)) )\n",
    "        return actions_with_tile_num\n",
    "\n",
    "    # 根据旧的state和action返回新的state\n",
    "    def successor(self, state, action):\n",
    "        old0row, old0col  =  state[0]    # get start position\n",
    "        new0row, new0col, move = action  # unpack the action representation\n",
    "        moving_number, _ = move\n",
    "        ## Make a copy of the old layout\n",
    "        newlayout = deepcopy(state[1])\n",
    "        # Swap the positions of the new number and the space (rep by 0)\n",
    "        newlayout[old0row][old0col] = moving_number\n",
    "        newlayout[new0row][new0col] = 0\n",
    "        return ((new0row, new0col), newlayout )\n",
    "    \n",
    "    def goal_test(self,state):\n",
    "        return state[1] == self.goal_layout\n",
    "    \n",
    "    def display_action(self, action):\n",
    "        _,_, move = action\n",
    "        tile_num, direction = move\n",
    "        print(\"Move tile\", tile_num, direction)\n",
    "        \n",
    "    def display_state(self,state):\n",
    "        for row in state[1]:\n",
    "            nums = [ (n if n>0 else '.') for n in row]\n",
    "            print( \"   \", nums[0], nums[1], nums[2] )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "iT4rmbIJWO0u"
   },
   "source": [
    "### Constructing a problem instance\n",
    "We can now create a `EightPuzzle` instance by giving its initial layout and goal layout:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "a8dWjjniWO0u"
   },
   "outputs": [],
   "source": [
    "EP = EightPuzzle( LAYOUT_1, NORMAL_GOAL )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "l-YyR8gtWO0u"
   },
   "source": [
    "## Running the `search` function\n",
    "\n",
    "Now we can try running the search function. Let's start with a breadth first search. It should be able to fund an optimal path to the solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 417
    },
    "id": "YaNMU7UVWO0u",
    "outputId": "0eb2364a-4e6e-40ab-b4d7-046d145f7595"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is the general SearchProblem parent class\n",
      "You must extend this class to encode a particular search problem.\n",
      "\n",
      "** Running Brandon's Search Algorithm **\n",
      "Strategy: mode=BF/FIFO, cost=None, heuristic=None\n",
      "Max search nodes: 1000000  (max number added to queue)\n",
      "Searching (will output '.' each 1000 goal_tests)\n",
      ".................................................................................................... (100000)\n",
      ".................................................................................................... (200000)\n",
      ".................................................................................................... (300000)\n",
      "..........................................................\n",
      "!! Search node limit (1000000) reached !!\n",
      "): No solution found :(\n",
      "\n",
      "\n",
      "SEARCH SPACE STATS:\n",
      "Total nodes generated          =  1000001  (includes start)\n",
      "Nodes tested (by goal_test)    =   358301  (all expanded)\n",
      "Nodes left in queue            =   641699\n",
      "\n",
      "Time taken = 51.9127 seconds\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'NODE_LIMIT_EXCEEDED'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search(EP, 'BF/FIFO', 1000000, loop_check=False, show_state_path=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "IkgnnNSVWO0v"
   },
   "source": [
    "Hmm... What happened?\n",
    "\n",
    "Maybe we should try something else. How about the `loop_check` option?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "8ENWuwZJWO0v"
   },
   "source": [
    "## Using Heuristics\n",
    "\n",
    "Another way to help the search algorithm work more effectively is of course by using a heuristic to guide the selection of moves to explore while searching for a solution.\n",
    "\n",
    "In the notes (and in Russell and Norvig) you will have seen mention of the _misplaced tiles_ heuristic and the _manhattan distance_ heuristic. You should know enough to be able to implement these your self. You just need to define a function that takes a state  as its argument and returns the corresponding value of the heuristic applied to that state. (Remember that the state representation consists of the space position and the tile layout, as described above.)\n",
    "\n",
    "But to save you the trouble for the time being and let you see the effect of these heuristics, I have pre-defined them for you in my Python module `crazy8heuristics`.\n",
    "The following cell should install that module and import functions for the heuristics `bb_misplaced_tiles` and `bb_manhattan`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "jPXmWwMjWO0v",
    "outputId": "bb2ded2b-b0e0-4bf4-e258-1b32b6b23c08"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100  4731  100  4731    0     0   3684      0  0:00:01  0:00:01 --:--:--  3681\n"
     ]
    }
   ],
   "source": [
    "!mkdir -p bbmodcache\n",
    "!curl http://bb-ai.net.s3.amazonaws.com/bb-python-modules/crazy8heuristics.py > bbmodcache/crazy8heuristics.py\n",
    "from bbmodcache.crazy8heuristics import bb_misplaced_tiles, bb_manhattan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "dQ-0XNEHWO0w"
   },
   "source": [
    "Note that the heuristics defined in `craz8heuristics` are based on the assumption that the goal is to get to a state with the `NORMAL_GOAL` tile layout, as specified above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6dr_DOcbWO0w"
   },
   "source": [
    "### Running `search` with a heuristics\n",
    "We can now add one of the heuristics as an option to the `search` function, as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "GvzA1F_SWO0w",
    "outputId": "fcff75da-e746-4ac6-d5fa-beda4e5e1dd9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is the general SearchProblem parent class\n",
      "You must extend this class to encode a particular search problem.\n",
      "\n",
      "** Running Brandon's Search Algorithm **\n",
      "Strategy: mode=BF/FIFO, cost=None, heuristic=bb_misplaced_tiles\n",
      "Max search nodes: 1000000  (max number added to queue)\n",
      "Searching (will output '.' each 1000 goal_tests)\n",
      "\n",
      ":-)) *SUCCESS* ((-:\n",
      "\n",
      "Path length = 38\n",
      "Goal state is:\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 8 .\n",
      "The action path to the solution is:\n",
      "Move tile 3 right\n",
      "Move tile 6 right\n",
      "Move tile 2 down\n",
      "Move tile 4 left\n",
      "Move tile 8 left\n",
      "Move tile 3 up\n",
      "Move tile 6 right\n",
      "Move tile 8 down\n",
      "Move tile 1 down\n",
      "Move tile 7 left\n",
      "Move tile 3 up\n",
      "Move tile 6 up\n",
      "Move tile 8 right\n",
      "Move tile 2 right\n",
      "Move tile 4 down\n",
      "Move tile 5 down\n",
      "Move tile 7 left\n",
      "Move tile 1 up\n",
      "Move tile 5 right\n",
      "Move tile 7 down\n",
      "Move tile 1 left\n",
      "Move tile 5 up\n",
      "Move tile 7 right\n",
      "Move tile 4 up\n",
      "Move tile 2 left\n",
      "Move tile 7 down\n",
      "Move tile 5 down\n",
      "Move tile 1 right\n",
      "Move tile 4 up\n",
      "Move tile 2 up\n",
      "Move tile 7 left\n",
      "Move tile 5 down\n",
      "Move tile 2 right\n",
      "Move tile 4 down\n",
      "Move tile 1 left\n",
      "Move tile 2 up\n",
      "Move tile 5 up\n",
      "Move tile 8 left\n",
      "\n",
      "The state/action path to the solution is:\n",
      "    5 1 7\n",
      "    2 4 8\n",
      "    6 3 .\n",
      "Move tile 3 right\n",
      "    5 1 7\n",
      "    2 4 8\n",
      "    6 . 3\n",
      "Move tile 6 right\n",
      "    5 1 7\n",
      "    2 4 8\n",
      "    . 6 3\n",
      "Move tile 2 down\n",
      "    5 1 7\n",
      "    . 4 8\n",
      "    2 6 3\n",
      "Move tile 4 left\n",
      "    5 1 7\n",
      "    4 . 8\n",
      "    2 6 3\n",
      "Move tile 8 left\n",
      "    5 1 7\n",
      "    4 8 .\n",
      "    2 6 3\n",
      "Move tile 3 up\n",
      "    5 1 7\n",
      "    4 8 3\n",
      "    2 6 .\n",
      "Move tile 6 right\n",
      "    5 1 7\n",
      "    4 8 3\n",
      "    2 . 6\n",
      "Move tile 8 down\n",
      "    5 1 7\n",
      "    4 . 3\n",
      "    2 8 6\n",
      "Move tile 1 down\n",
      "    5 . 7\n",
      "    4 1 3\n",
      "    2 8 6\n",
      "Move tile 7 left\n",
      "    5 7 .\n",
      "    4 1 3\n",
      "    2 8 6\n",
      "Move tile 3 up\n",
      "    5 7 3\n",
      "    4 1 .\n",
      "    2 8 6\n",
      "Move tile 6 up\n",
      "    5 7 3\n",
      "    4 1 6\n",
      "    2 8 .\n",
      "Move tile 8 right\n",
      "    5 7 3\n",
      "    4 1 6\n",
      "    2 . 8\n",
      "Move tile 2 right\n",
      "    5 7 3\n",
      "    4 1 6\n",
      "    . 2 8\n",
      "Move tile 4 down\n",
      "    5 7 3\n",
      "    . 1 6\n",
      "    4 2 8\n",
      "Move tile 5 down\n",
      "    . 7 3\n",
      "    5 1 6\n",
      "    4 2 8\n",
      "Move tile 7 left\n",
      "    7 . 3\n",
      "    5 1 6\n",
      "    4 2 8\n",
      "Move tile 1 up\n",
      "    7 1 3\n",
      "    5 . 6\n",
      "    4 2 8\n",
      "Move tile 5 right\n",
      "    7 1 3\n",
      "    . 5 6\n",
      "    4 2 8\n",
      "Move tile 7 down\n",
      "    . 1 3\n",
      "    7 5 6\n",
      "    4 2 8\n",
      "Move tile 1 left\n",
      "    1 . 3\n",
      "    7 5 6\n",
      "    4 2 8\n",
      "Move tile 5 up\n",
      "    1 5 3\n",
      "    7 . 6\n",
      "    4 2 8\n",
      "Move tile 7 right\n",
      "    1 5 3\n",
      "    . 7 6\n",
      "    4 2 8\n",
      "Move tile 4 up\n",
      "    1 5 3\n",
      "    4 7 6\n",
      "    . 2 8\n",
      "Move tile 2 left\n",
      "    1 5 3\n",
      "    4 7 6\n",
      "    2 . 8\n",
      "Move tile 7 down\n",
      "    1 5 3\n",
      "    4 . 6\n",
      "    2 7 8\n",
      "Move tile 5 down\n",
      "    1 . 3\n",
      "    4 5 6\n",
      "    2 7 8\n",
      "Move tile 1 right\n",
      "    . 1 3\n",
      "    4 5 6\n",
      "    2 7 8\n",
      "Move tile 4 up\n",
      "    4 1 3\n",
      "    . 5 6\n",
      "    2 7 8\n",
      "Move tile 2 up\n",
      "    4 1 3\n",
      "    2 5 6\n",
      "    . 7 8\n",
      "Move tile 7 left\n",
      "    4 1 3\n",
      "    2 5 6\n",
      "    7 . 8\n",
      "Move tile 5 down\n",
      "    4 1 3\n",
      "    2 . 6\n",
      "    7 5 8\n",
      "Move tile 2 right\n",
      "    4 1 3\n",
      "    . 2 6\n",
      "    7 5 8\n",
      "Move tile 4 down\n",
      "    . 1 3\n",
      "    4 2 6\n",
      "    7 5 8\n",
      "Move tile 1 left\n",
      "    1 . 3\n",
      "    4 2 6\n",
      "    7 5 8\n",
      "Move tile 2 up\n",
      "    1 2 3\n",
      "    4 . 6\n",
      "    7 5 8\n",
      "Move tile 5 up\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 . 8\n",
      "Move tile 8 left\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 8 .\n",
      "\n",
      "SEARCH SPACE STATS:\n",
      "Total nodes generated          =      709  (includes start)\n",
      "Nodes discarded by loop_check  =      283  (426 distinct states added to queue)\n",
      "Nodes tested (by goal_test)    =      259  (258 expanded + 1 goal)\n",
      "Nodes left in queue            =      167\n",
      "\n",
      "Time taken = 0.0551 seconds\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GOAL_STATE_FOUND'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search(EP, 'BF/FIFO', 1000000, heuristic=bb_misplaced_tiles, \n",
    "       loop_check=True, show_state_path=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "cw6Y0u4EWO0w"
   },
   "source": [
    "You should also try using the `bb_manhattan` heursitic and compare the results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "hpnEQRbqWO0x"
   },
   "source": [
    "## Heuristic Evaluation Exercise\n",
    "\n",
    "Can you answer the following questions?\n",
    "\n",
    "* Were solution path sequences found? \n",
    "* If so were they good solutions?\n",
    "* Did the heuristics improve performance?\n",
    "* Was one better than the other?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "PNEKlK_qWO0x"
   },
   "source": [
    "## What about using a cost function ?\n",
    "\n",
    "Another way we can guide the way a search space is explored is by using a cost function that gives some measure of the cost of getting to a given state by going along a given path from the start point of the search.\n",
    "\n",
    "But in the 8-Puzzle all moves are just sliding one tile into a space, so we would probably consider all moves to have equal cost. Hence, the cost of getting to any state along any path would just be the length of the path.\n",
    "\n",
    "Well, at least this is easy to implement, as we see below. But is it useful?\n",
    "Let us try it and let us compare what happens with the cost function set with what happens without any cost function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "J3GUqRj9WO0x",
    "outputId": "caaff600-84f5-49a9-ba4c-75157ff76c7d"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is the general SearchProblem parent class\n",
      "You must extend this class to encode a particular search problem.\n",
      "\n",
      "** Running Brandon's Search Algorithm **\n",
      "Strategy: mode=BF/FIFO, cost=cost, heuristic=bb_manhattan\n",
      "Max search nodes: 100000  (max number added to queue)\n",
      "Searching (will output '.' each 1000 goal_tests)\n",
      ".......\n",
      ":-)) *SUCCESS* ((-:\n",
      "\n",
      "Path length = 28\n",
      "Goal state is:\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 8 .\n",
      "Cost of reaching goal: 28\n",
      "The action path to the solution is:\n",
      "Move tile 3 right\n",
      "Move tile 4 down\n",
      "Move tile 2 right\n",
      "Move tile 6 up\n",
      "Move tile 4 left\n",
      "Move tile 3 left\n",
      "Move tile 8 down\n",
      "Move tile 2 right\n",
      "Move tile 6 right\n",
      "Move tile 5 down\n",
      "Move tile 1 left\n",
      "Move tile 7 left\n",
      "Move tile 2 up\n",
      "Move tile 6 right\n",
      "Move tile 3 up\n",
      "Move tile 8 left\n",
      "Move tile 6 down\n",
      "Move tile 3 right\n",
      "Move tile 7 down\n",
      "Move tile 2 left\n",
      "Move tile 3 up\n",
      "Move tile 6 up\n",
      "Move tile 8 right\n",
      "Move tile 7 down\n",
      "Move tile 5 right\n",
      "Move tile 4 up\n",
      "Move tile 7 left\n",
      "Move tile 8 left\n",
      "\n",
      "The state/action path to the solution is:\n",
      "    5 1 7\n",
      "    2 4 8\n",
      "    6 3 .\n",
      "Move tile 3 right\n",
      "    5 1 7\n",
      "    2 4 8\n",
      "    6 . 3\n",
      "Move tile 4 down\n",
      "    5 1 7\n",
      "    2 . 8\n",
      "    6 4 3\n",
      "Move tile 2 right\n",
      "    5 1 7\n",
      "    . 2 8\n",
      "    6 4 3\n",
      "Move tile 6 up\n",
      "    5 1 7\n",
      "    6 2 8\n",
      "    . 4 3\n",
      "Move tile 4 left\n",
      "    5 1 7\n",
      "    6 2 8\n",
      "    4 . 3\n",
      "Move tile 3 left\n",
      "    5 1 7\n",
      "    6 2 8\n",
      "    4 3 .\n",
      "Move tile 8 down\n",
      "    5 1 7\n",
      "    6 2 .\n",
      "    4 3 8\n",
      "Move tile 2 right\n",
      "    5 1 7\n",
      "    6 . 2\n",
      "    4 3 8\n",
      "Move tile 6 right\n",
      "    5 1 7\n",
      "    . 6 2\n",
      "    4 3 8\n",
      "Move tile 5 down\n",
      "    . 1 7\n",
      "    5 6 2\n",
      "    4 3 8\n",
      "Move tile 1 left\n",
      "    1 . 7\n",
      "    5 6 2\n",
      "    4 3 8\n",
      "Move tile 7 left\n",
      "    1 7 .\n",
      "    5 6 2\n",
      "    4 3 8\n",
      "Move tile 2 up\n",
      "    1 7 2\n",
      "    5 6 .\n",
      "    4 3 8\n",
      "Move tile 6 right\n",
      "    1 7 2\n",
      "    5 . 6\n",
      "    4 3 8\n",
      "Move tile 3 up\n",
      "    1 7 2\n",
      "    5 3 6\n",
      "    4 . 8\n",
      "Move tile 8 left\n",
      "    1 7 2\n",
      "    5 3 6\n",
      "    4 8 .\n",
      "Move tile 6 down\n",
      "    1 7 2\n",
      "    5 3 .\n",
      "    4 8 6\n",
      "Move tile 3 right\n",
      "    1 7 2\n",
      "    5 . 3\n",
      "    4 8 6\n",
      "Move tile 7 down\n",
      "    1 . 2\n",
      "    5 7 3\n",
      "    4 8 6\n",
      "Move tile 2 left\n",
      "    1 2 .\n",
      "    5 7 3\n",
      "    4 8 6\n",
      "Move tile 3 up\n",
      "    1 2 3\n",
      "    5 7 .\n",
      "    4 8 6\n",
      "Move tile 6 up\n",
      "    1 2 3\n",
      "    5 7 6\n",
      "    4 8 .\n",
      "Move tile 8 right\n",
      "    1 2 3\n",
      "    5 7 6\n",
      "    4 . 8\n",
      "Move tile 7 down\n",
      "    1 2 3\n",
      "    5 . 6\n",
      "    4 7 8\n",
      "Move tile 5 right\n",
      "    1 2 3\n",
      "    . 5 6\n",
      "    4 7 8\n",
      "Move tile 4 up\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    . 7 8\n",
      "Move tile 7 left\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 . 8\n",
      "Move tile 8 left\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 8 .\n",
      "\n",
      "SEARCH SPACE STATS:\n",
      "Total nodes generated          =    19022  (includes start)\n",
      "Nodes discarded by loop_check  =     8094  (10928 distinct states added to queue)\n",
      "Nodes tested (by goal_test)    =     7165  (7164 expanded + 1 goal)\n",
      "Nodes left in queue            =     3763\n",
      "\n",
      "Time taken = 0.5737 seconds\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GOAL_STATE_FOUND'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def cost(path, state):\n",
    "        return len(path)\n",
    "\n",
    "\n",
    "search(EP, 'BF/FIFO', 100000, cost=cost, heuristic=bb_manhattan, loop_check=True, show_state_path=True)\n",
    "#search(EP, 'BF/FIFO', 100000, loop_check=True, show_state_path=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5IIq_8suWO0x"
   },
   "source": [
    "## What else can we try? How about A* ?\n",
    "\n",
    "Probably you found that using a cost function was a bit of a disapointment.\n",
    "If the cost is the same for every action, the effect will be the same as running a simple breadth-first search.\n",
    "\n",
    "However, there is one more thing we should try. The __A*__ algorithm uses both a cost function and a heuristic to estimate the total cost of a path running through a node and gives priority to states with the lowest sum of both the cost and the heuristic.\n",
    "\n",
    "You should try that. And by now you should have seen enough examples of using the `search` function to write the code for doing __A*__. All you need to do is specify functions for both the `cost` option and the `heuristic` option. Go to it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "TIOFbkLFWO0y"
   },
   "outputs": [],
   "source": [
    "## Specify and execute an A* search run here:\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "yHKpjfxrWO0y"
   },
   "source": [
    "Assuming that worked, you should perhaps compare the effectiveness of the two different heuristics: _misplaced tiles_ and _Manhattan distance_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "CI9t1dhuWO0y"
   },
   "source": [
    "## Designing a systematic search algorithm testing experiment\n",
    "\n",
    "In order to give a general analysis of how different search algorithms perform when applied to a problem, it is essential idea to have a clear and concise record of the tests that will be or were carried out during the investigation.\n",
    "If the tests are carried out within a software system, an easy way to do this is to define the whole sequence of tests within a single file or within a function defination. Or, since I am using a Notebook file, I can simply specify sequence of test runs of the `search` function together within a code cell, as in the following cell. \n",
    "\n",
    "Note that I have set the `return_info` option to `True` and am catching the information resturned by assigning the results to variables (`T1` and `T2`). \n",
    "And I have also set `dots=False`, which turns of the display of dots indicating progress of the search. You may not want to see the dots every time you run a given test.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "egHEOsN4WO0y",
    "outputId": "8bbd181e-79bb-4683-bb94-08c28bbcd272"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is the general SearchProblem parent class\n",
      "You must extend this class to encode a particular search problem.\n",
      "\n",
      "** Running Brandon's Search Algorithm **\n",
      "Strategy: mode=BF/FIFO, cost=None, heuristic=None\n",
      "Max search nodes: 10000  (max number added to queue)\n",
      "Search started (progress dot output off)\n",
      "\n",
      "!! Search node limit (10000) reached !!\n",
      "): No solution found :(\n",
      "\n",
      "\n",
      "SEARCH SPACE STATS:\n",
      "Total nodes generated          =    10001  (includes start)\n",
      "Nodes tested (by goal_test)    =     3605  (all expanded)\n",
      "Nodes left in queue            =     6395\n",
      "\n",
      "Time taken = 0.1536 seconds\n",
      "\n",
      "This is the general SearchProblem parent class\n",
      "You must extend this class to encode a particular search problem.\n",
      "\n",
      "** Running Brandon's Search Algorithm **\n",
      "Strategy: mode=BF/FIFO, cost=None, heuristic=None\n",
      "Max search nodes: 1000000  (max number added to queue)\n",
      "Search started (progress dot output off)\n",
      "\n",
      ":-)) *SUCCESS* ((-:\n",
      "\n",
      "Path length = 28\n",
      "Goal state is:\n",
      "    1 2 3\n",
      "    4 5 6\n",
      "    7 8 .\n",
      "The action path to the solution is:\n",
      "Move tile 3 right\n",
      "Move tile 6 right\n",
      "Move tile 2 down\n",
      "Move tile 4 left\n",
      "Move tile 8 left\n",
      "Move tile 7 down\n",
      "Move tile 1 right\n",
      "Move tile 5 right\n",
      "Move tile 4 up\n",
      "Move tile 8 left\n",
      "Move tile 7 left\n",
      "Move tile 3 up\n",
      "Move tile 6 right\n",
      "Move tile 2 right\n",
      "Move tile 8 down\n",
      "Move tile 7 left\n",
      "Move tile 5 down\n",
      "Move tile 1 left\n",
      "Move tile 3 up\n",
      "Move tile 5 right\n",
      "Move tile 2 up\n",
      "Move tile 8 right\n",
      "Move tile 7 down\n",
      "Move tile 4 down\n",
      "Move tile 1 left\n",
      "Move tile 2 up\n",
      "Move tile 5 left\n",
      "Move tile 6 up\n",
      "\n",
      "\n",
      "SEARCH SPACE STATS:\n",
      "Total nodes generated          =   475687  (includes start)\n",
      "Nodes discarded by loop_check  =   294833  (180854 distinct states added to queue)\n",
      "Nodes tested (by goal_test)    =   178053  (178052 expanded + 1 goal)\n",
      "Nodes left in queue            =     2801\n",
      "\n",
      "Time taken = 9.6926 seconds\n",
      "\n"
     ]
    }
   ],
   "source": [
    "prob1 = EightPuzzle( LAYOUT_1, NORMAL_GOAL )\n",
    "\n",
    "T1 = search(prob1, 'BF/FIFO', 10000,   loop_check=False, dots=False, return_info=True)\n",
    "T2 = search(prob1, 'BF/FIFO', 1000000, loop_check=True,  dots=False, return_info=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EWIi7u5NWO0y"
   },
   "source": [
    "## Examining and Presenting Results\n",
    "The result returned by `search` when `return_info` is set to `True` contains a lot of information about the test that was run, the outcome obtained, the time taken and the size of the search space explored in terms of numbers of notdes generated, tested, left in the queue (and also those 'discarded' if the `loop_check` is set to `True`).\n",
    "\n",
    "Let us look at the info returned from test `T2`. (The `display` function is an inbuilt notebook function that is intended to present data objects in a way that is easily comprehensible by software developers.) The value of `T2` is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 798
    },
    "id": "wLdA_PFUWO0y",
    "outputId": "042f8d7f-f30a-4836-d165-2ddc1bdaac69"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'args': {'problem': 'EightPuzzle',\n",
       "  'mode': 'BF/FIFO',\n",
       "  'max_nodes': 1000000,\n",
       "  'loop_check': True,\n",
       "  'randomise': False,\n",
       "  'cost': None,\n",
       "  'heuristic': None,\n",
       "  'dots': False},\n",
       " 'result': {'termination_condition': 'GOAL_STATE_FOUND',\n",
       "  'goal_state': ((2, 2), [[1, 2, 3], [4, 5, 6], [7, 8, 0]]),\n",
       "  'path': [(2, 1, (3, 'right')),\n",
       "   (2, 0, (6, 'right')),\n",
       "   (1, 0, (2, 'down')),\n",
       "   (1, 1, (4, 'left')),\n",
       "   (1, 2, (8, 'left')),\n",
       "   (0, 2, (7, 'down')),\n",
       "   (0, 1, (1, 'right')),\n",
       "   (0, 0, (5, 'right')),\n",
       "   (1, 0, (4, 'up')),\n",
       "   (1, 1, (8, 'left')),\n",
       "   (1, 2, (7, 'left')),\n",
       "   (2, 2, (3, 'up')),\n",
       "   (2, 1, (6, 'right')),\n",
       "   (2, 0, (2, 'right')),\n",
       "   (1, 0, (8, 'down')),\n",
       "   (1, 1, (7, 'left')),\n",
       "   (0, 1, (5, 'down')),\n",
       "   (0, 2, (1, 'left')),\n",
       "   (1, 2, (3, 'up')),\n",
       "   (1, 1, (5, 'right')),\n",
       "   (2, 1, (2, 'up')),\n",
       "   (2, 0, (8, 'right')),\n",
       "   (1, 0, (7, 'down')),\n",
       "   (0, 0, (4, 'down')),\n",
       "   (0, 1, (1, 'left')),\n",
       "   (1, 1, (2, 'up')),\n",
       "   (1, 2, (5, 'left')),\n",
       "   (2, 2, (6, 'up'))],\n",
       "  'path_length': 28},\n",
       " 'search_stats': {'nodes_generated': 475687,\n",
       "  'nodes_tested': 178053,\n",
       "  'nodes_discarded': 294833,\n",
       "  'distinct_states_seen': 180854,\n",
       "  'nodes_left_in_queue': 2801,\n",
       "  'time_taken': 9.692641833000003}}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(T2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "PTQITIAuWO0z"
   },
   "source": [
    "### Comparing results by generating a table\n",
    "\n",
    "The results in the for displayed in the previous cell are not very easy to interpret and certainly do not facilitate comparison between different types of search.\n",
    "To do that we may want to compile a table that presents key information in a clear and systemmatic way. The following cell contains a simple example of how we can do this by looping through a list of test results and printing out certain values taken from the search results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "Fk81BPw8WO0z",
    "outputId": "dcb7cec1-1a51-4a8c-e885-6ffd835ccab7"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "                **TESTS SUMMARY**\n",
      "\n",
      "Test    #max   Result   #gen     #inQ    Time s\n",
      "  0:    10000    !     10001     6395     0.15 \n",
      "  1:  1000000    Y    475687     2801     9.69 \n"
     ]
    }
   ],
   "source": [
    "TEST_RESULTS =[T1, T2]\n",
    "\n",
    "short_tc = {\"GOAL_STATE_FOUND\"     : \"Y\",\n",
    "            \"NODE_LIMIT_EXCEEDED\"  : \"!\",\n",
    "            \"SEARH-SPACE_EXHAUSTED\": \"x\"}\n",
    "\n",
    "print(\"\\n                **TESTS SUMMARY**\\n\")\n",
    "\n",
    "print(\"Test    #max   Result   #gen     #inQ    Time s\")\n",
    "for i, test in enumerate(TEST_RESULTS):\n",
    "    max  = test['args']['max_nodes']\n",
    "    tc  = test['result']['termination_condition']\n",
    "    stc = short_tc[tc]\n",
    "    \n",
    "    ng  = test['search_stats']['nodes_generated']\n",
    "    nq  = test['search_stats']['nodes_left_in_queue']\n",
    "    time = round( test['search_stats']['time_taken'], 2 )\n",
    "    print( f\"{i:>3}: {max:>8}    {stc}  {ng:>8} {nq:>8}     {time} \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "o2aU9d3VWO0z"
   },
   "source": [
    "Not bad! But maybe should show solution path lengths as well?"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "SearchExercise6.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
